{\magonebf 6.6 Planar Subdivisions (subdivision)}

An instance $S$ of the data type $subdivision$ is a subdivision of the 
two-dimensional plane, i.e., an embedded planar graph with straight
line edges (see also sections 5.3 and 5.6). With each node $v$ of $S$ is 
associated a point, called the position of $v$ and with each face of $S$ 
is associated an information from a data type $I$, called the information 
type of $S$.


{\bf 1. Declaration}

\decl subdivision I 

introduces a new data type with name \name\ consisting of all 
planar subdivisions with information type $I$. 
\precond The data type $GRAPH(point,I)$ has been declared before.



{\bf 2. Creation of a subdivision}

\create S (GRAPH(point,I)\ G)

creates an instance \var\ of type \name\ and initializes it to 
the subdivision represented by the parameterized directed graph $G$. 
The node entries of $G$ (of type point)  define the positions of the 
corresponding nodes of \var. Every face $f$ of \var\ is assigned the 
information of one of its bounding edges in $G$.  \precond $G$ represents 
a planar subdivision, i.e., a straight line embedded planar map.


\bigskip
{\bf 2. \operations}
\medskip
\+\op point  position {node\ v}       { returns the position of node $v$.}
\smallskip
\+\op ftype  inf      {face\ f}       { returns the information of face $f$.}
\smallskip
\+\op face   locate\_point {point\ p} { returns the face containing point $p$.}
\smallskip


\bigskip
{\bf 3. Implementation}

Planar subdivisions are implemented by parameterized planar maps and an
additional data structure for point location. Operations position and inf
take constant time, a locate\_point operation takes time $O(\log^2 n)$.
Here $n$ is the number of nodes.  The space requiremnt and the 
initialization time is $O(n^2)$.

